package LeetCode;

/**
 * 以x为基准分割连表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 思路：声明两个小链表，small,big;所有小于x的节点链接在small,所有>=的节点连接在big
 * 最后让small与big一合并就好【边遍历原链表边将原链表的节点依次根据与x的大小关系分别放在small与big中】
 */
public class Num0204 {
    public ListNode partition(ListNode head, int x) {
        //创建small和big两个小链表的头节点【虚拟头节点】
        ListNode smallHead=new ListNode(-1);
        ListNode bigHead=new ListNode(-1);
        //按照升序插入，需要尾插
        //再用两个引用分别指向子链表的尾部
        ListNode smallTail=smallHead;
        ListNode bigTail=bigHead;
        //开始遍历：边遍历原链表，边根据值将节点依次放在两个子链表中
        while(head!=null){
            if(head.val<x){//小于放在small，尾插
                smallTail.next=head;
                smallTail=head;
            }else{
                bigTail.next=head;
                bigTail=head;
            }
            head=head.next;//原链表后移更新
        }
        //遍历完链表后bigtail尾部元素得置空
        bigTail.next=null;
        //拼接小链表与大链表[smallTail是small的尾部，bigHead.next是big的头部]
        smallTail.next=bigHead.next;
        //返回
        return smallHead.next;
    }
}
